/*
 * [25]  合并两个排序的链表
 * 
 * Input: 1->2->4, 1->3->4
 * Output: 1->1->2->3->4->4
 * 
 *
 * g++ test_cpp.cpp -ggdb -std=c++11
 */

// @lc code=start

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <stack>

using namespace std;

// Definition for singly-linked list.
struct ListNode
{
  int val;
  struct ListNode *pnext;
  ListNode(int x) : val(x), pnext(NULL)
  {
  }
};

class Solution
{
public:
  // 在首结点head之前是头结点prehead
  ListNode *mergeTwoLists(ListNode *l1, ListNode *l2)
  {
    if (l1 == nullptr)
      return l2;
    if (l2 == nullptr)
      return l1;

    // 首结点前面附加一结点（当原链表首结点可能会变化时都可以考虑使用prehead）
    ListNode prehead(0);

    // 新链表结点指针
    ListNode *p = &prehead;
    // 比较l1和l2各结点大小，归并
    for (; l1 != nullptr && l2 != nullptr; p = p->pnext)
    {
      if (l1->val < l2->val)
      {
        // p指向的prehead的指针域挂l1
        p->pnext = l1;
        l1 = l1->pnext;
      }
      else
      {
        p->pnext = l2;
        l2 = l2->pnext;
      }
    }

    // 如果提前比较完
    // l2提前比较完
    if (l1 != nullptr)
      p->pnext = l1;
    // 提前比较完
    if (l2 != nullptr)
      p->pnext = l2;

    return prehead.pnext;
  }
};

int main()
{
  class Solution solute;
  ListNode *prehead = new ListNode(-1);

  ListNode *head = new ListNode(1);
  prehead->pnext = head;

  ListNode *node2 = new ListNode(2);
  head->pnext = node2;
  node2->pnext = nullptr;

  ListNode *node3 = new ListNode(2);
  node2->pnext = node3;
  node3->pnext = nullptr;

  ListNode *node4 = new ListNode(3);
  node3->pnext = node4;
  node4->pnext = nullptr;

  ListNode *node5 = new ListNode(5);
  node4->pnext = node5;
  node5->pnext = nullptr;

  ListNode *prehead2 = new ListNode(-1);

  ListNode *head2 = new ListNode(1);
  prehead2->pnext = head2;

  ListNode *node_2 = new ListNode(2);
  head2->pnext = node_2;
  node_2->pnext = nullptr;

  ListNode *entry = solute.mergeTwoLists(head, head2);

  return 0;
}

// @lc code=end
